package leetcode;

public class Leetcode1140 {
    public String stoneGameIII(int[] stoneValue) {
        int n = stoneValue.length;
        Integer[] dp = new Integer[stoneValue.length];
        int score = dfs(stoneValue,0,dp);
        System.out.println(score);
        if(score>0){
            return "Alice";
        }else if(score<0){
            return "Bob";
        }else{
            return "Tie";
        }

    }

    public int dfs(int[] stoneValue,int left,Integer[] dp){
        if(left==stoneValue.length){
            return 0;
        }
        if(dp[left]!=null){
            return dp[left];
        }
        int max = Integer.MIN_VALUE;
        int sum = 0;
        for(int i = left;i<left+3&&i<stoneValue.length;i++){
            sum = sum + stoneValue[i];
            max = Math.max(max,sum-dfs(stoneValue,i+1,dp));
        }
        return dp[left] = max;
    }


}
